#include <cstdlib>
#include <iostream>
#include<cstdio>
#include <cstring>
using namespace std;

unsigned int X,Y,K,B;
unsigned int c[35];
unsigned int f[35][35];

void init()
{
 f[0][0] = 1;
 for(unsigned int i=1;i<=31;i++)
 {
  f[i][0] = f[i-1][0];
  for(unsigned int j = 1;j<=i;j++)
   f[i][j] = f[i-1][j]+f[i-1][j-1];
 }
}
void changetoBin(unsigned int & x)
{
 memset(&c,0,sizeof(c));
  int i = 0,j = 0;
 for(;x!=0;x/=B,i++)
  c[i] = x % B;
 i--;
 for(j = i;j>=0;j--)
  if(c[j] >1)
   break;
 for( int k = j;k>=0;k--)
  c[k] = 1;
 x = 0;
 for( int k = i;k>=0;k--)
 {
  x *= 2;
  x += c[k];
 }
}
unsigned int calc(unsigned int m)
{
 unsigned int tot = 0;
 unsigned int x = 0;
 for( int i = 31;i>=0;i--)
   if((m & (1U<<i)) )
   {
    tot += f[i][K-x];
    x++;
    if(x > K)
     break;
    m ^= (1U<<i);
   }

 return tot;
}
int main()
{
    scanf("%d%d%d%d",&X,&Y,&K,&B);
    init();
    changetoBin(X);
    changetoBin(Y);
    printf("%d",calc(Y+1)-calc(X));

    return EXIT_SUCCESS;
}
